package cn.myworld.algorithm.sort;

import cn.myworld.algorithm.common.BaseSort;

/**
 * 希尔排序
 */
public class Shell extends BaseSort {

    public static void sort(Comparable[] a) {
        // 1.根据数组a的长度确定增长量h的初始值
        int h = 1;
        while (h < a.length / 2) {
            h = 2 * h + 1;
        }
        // 2.希尔排序
        while (h >= 1) {
            // 排序
            // 找到待插入的元素
            for (int i = h; i < a.length; i++) {
                // 把待插入元素插入到有序数列中
                for (int j = i; j >= h; j -= h) {
                    // 待插入的元素是a[j]，比较a[j]和a[j-h]
                    if (greater(a[j - h], a[j])) {
                        // 交换元素
                        exch(a, j-h, j);
                    } else {
                        // 待插入元素已经找到了合适的位置
                        break;
                    }
                }
            }

            // 减小h的值
            h /= 2;
        }
    }

}
